package com.leetcode.tree.traversal;

import com.leetcode.basic.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/6/16 21:47
 */
public class InorderTraversal_94 {

    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            // 先检索所有的左子树结点，入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 取出栈顶元素
            TreeNode node = stack.pop();
            list.add(node.val);
            // 将右子树的元素进行遍历
            cur = node.right;
        }
        return list;
    }

    public List<Integer> morrisTraverse(TreeNode root) {
        final List<Integer> list = new ArrayList<>();
        while (root != null) {
            if (root.left != null) {
                final TreeNode node = getMostRight(root);
                if (node.right == null) {
                    // 找到最左端的结点，并且把它的右节点置为其父节点
                    node.right = root;
                    // 结点向左子节点移动
                    root = root.left;
                    // 这里注意直接跳到下一次循环 --- 也就是说，每次root都会遍历到最左端的子节点
                    continue;
                } else if (node.right == root) {
                    // 还原树的结构
                    node.right = null;
                }
            }
            list.add(root.val);
            // 这时右子节点除了是本身的右节点外，还会指向父节点，也就时根节点
            // 从而实现了 左 - 根 - 右的遍历方式
            root = root.right;
        }
        return list;
    }

    // 获得左节点的最右边的节点
    private TreeNode getMostRight(TreeNode root) {
        if (root.left == null) return root;
        TreeNode node = root.left;
        while (node.right != null && node.right != root) {
            node = node.right;
        }
        return node;
    }

}
